package main

import (
	"fmt"
	"sort"
)

// 768. 最多能完成排序的块 II
// 这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。

// arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

// 我们最多能将数组分成多少块？

// 和排序好的对比
// 如果两段内词频完全相同，则可以通过排序得到，可切一段

func maxChunksToSorted(arr []int) int {
	var res int

	n := len(arr)
	var clone = make([]int, n)
	copy(clone, arr)
	sort.Ints(clone)

	m := make(map[int]int) // 统计词频
	for i, tot := 0, 0; i < n; i++ {
		a, b := arr[i], clone[i]

		if v, ok := m[a]; ok && v == -1 {
			tot--
		} else {
			tot++
		}

		m[a]++

		if v, ok := m[b]; ok && v == 1 {
			tot--
		} else {
			tot++
		}
		m[b]--
		if tot == 0 {
			res++
		}

	}

	return res
}
func maxChunksToSorted1(arr []int) (res int) {
	st := []int{}
	for i := range arr {
		if len(st) == 0 || arr[i] >= st[len(st)-1] {
			st = append(st, arr[i])
		} else {
			max := st[len(st)-1]
			st = st[:len(st)-1]
			for len(st) > 0 && st[len(st)-1] > arr[i] {
				st = st[:len(st)-1]
			}
			st = append(st, max)
		}
	}
	return len(st)
}
func main() {
	arr := []int{5, 4, 3, 2, 1}
	res := maxChunksToSorted(arr)
	fmt.Println(res)
}
